package binary_tree.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 判断是否是严格平衡的树
 * @Author Stark
 * @Date 2022/2/22 10:07
 */
public class Num110_IsBalancedTree {
    //使用Map是为了记忆化搜索，避免重复计算高度值
    Map<TreeNode,Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int left = 0;
        int right = 0;
        if(map.containsKey(root.left)){
            left = map.get(root.left);
        }else{
            left = maxDepth(root.left);
            map.put(root.left,left);
        }
        if(map.containsKey(root.right)){
            right = map.get(root.right);
        }else{
            right = maxDepth(root.right);
            map.put(root.right,right);
        }

        if(Math.abs(left - right) > 1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = 1 + maxDepth(root.left);
        int right = 1 + maxDepth(root.right);
        return Math.max(left,right);
    }
}
